1. Field of Invention
The present invention relates to a method of interpolation between known values to find intermediate values.
2. Description of the Related Art
Interpolation has a number of applications, particularly in the field of image processing. A particularly important use is in color mapping: the taking of values in one color space and mapping them on to corresponding values in another color space. Color mapping is important, because different devices may function best or most naturally in a particular color space. For example, a scanner may advantageously use the additive color space RGB (Red, Green, Blue), whereas a printer may more advantageously use the subtractive color space CMY (Cyan, Magenta, Yellow). There are a large number of other color spaces in common use: CieLab, CMYK, YCbCr, LUV and LHS are examples. To allow devices using different color spaces to interact, a method is needed to convert data from the color space of one device to the color space of another.
Such conversions can generally be carried out with a mathematical formula (though not a trivial one, as such mappings will typically be non-linear). The most satisfactory approach to computation in such cases is to use a lookup table. The difficulty with using a lookup table is that this may need to be extremely largexe2x80x94for example, a full table for conversion from a 24 bit RGB color space to a 24 bit CMY color space would require 48 MByte of memory, which is clearly unacceptably large. The solution, set out in UK Patent 1369702 and U.S. Pat. No. 3,893,166, is to store in the table only a coarse (sparse) lattice of points in the color space, and to use linear interpolation to compute the values between these points. In this approach, only values for every 2N points are stored in each of the input dimensions (plus the last point in every dimension). Choice of N is importantxe2x80x94if low, then the table will be large, and if high, interpolation will not approximate with sufficient accuracy. If N=4, the conversion above is reduced in size to a more acceptable 14.4 KByte.
FIG. 1 illustrates the problem. Input color space components 1 are provided in three dimensions (a, b, c). For the values in each of these dimensions, the higher bits au,bu,cu (from the highest bit to bit N) are used to find a coarse lattice point 2, and more particularly the cube 3 in the coarse lattice containing the point of interest. The lowest bits al,bl,cl are then used to determine the output components 4 with values x,y,z in the output color space using interpolation.
A number of interpolation techniques have been developed. The best known is trilinear interpolation, which uses a weighted average of values at the eight vertices of a cube in the sparse lattice to obtain the output. Trilinear interpolation is shown in FIG. 2. Values are known for the coarse lattice points 21. In a first linear interpolation step, a weighted average is taken between one of the sets of points and another of the sets of points (at opposite faces of the cube formed by the coarse lattice points 21). This generates four first linear interpolation points 22 (though alternative choices 23, 24 could also have been made). The second linear interpolation step involves interpolation between these four points to give two second linear interpolation points 25 (using the earlier alternative choices for first linear interpolation points, again alternative second linear interpolation points 26, 27 could be chosen). Whichever route is followed, the third linear interpolation step between the two second linear interpolation points provides the third linear interpolation point 28 and hence the output value.
Trilinear interpolation, and most other known interpolation processes, require eight table accesses (essentially, one access for each vertex). An improvement on this is provided by radial interpolation, described in British Patent Application No. 9826975.6. Radial interpolation has the advantage that it requires only five table accesses, rather than eight. Various other interpolation approaches are known, but none of these provides any significant reduction in computational complexity.
It is desirable to try and still further improve interpolation by reducing further computational complexity, and in particular by reducing as far as possible the total memory consumption for processes such as color mapping.
Accordingly, the invention provides a method of determining a value for a function, comprising: establishing an n-dimensional lattice having a plurality of lattice points, the function having values at the lattice points, wherein n is a positive integer greater than or equal to two; recording values for a subset of the lattice points, the lattice points of the subset being known value lattice points; and establishing a value for a given lattice point by determining the values of only m of (n+1) known value lattice points defining an n-simplex touching or enclosing the given lattice point, wherein m is a positive integer equal to the number of n-simplexes of non-zero volume whose vertices consist of the given lattice point and n of the (n+1) known value lattice points, and by returning a weighted average of said m of the known value lattice points.
This approach is highly advantageous, as it ensures that the value for any given lattice point can be found with a maximum of (n+1) look up operations from the table of given value lattice points (the sparse lattice). If these look up operations have a critical effect on the performance of the overall systemxe2x80x94which may be the case, particularly where the values for the sparse lattice are packed, to minimize storage requirements - then this minimization of look up operations can have a real effect on speed, in particular.
While this approach is valid for n-dimensional spaces, it is of most interest here for three-dimensional spaces (as would typically be used in color mapping). The approach is particularly effective where n=3, and the known value lattice points define a tetrahedron. Four is now the maximum number of look up operations required.
Whereas four is a maximum number of look up operations required, for many cases preferred embodiments of the invention can reduce this number to three, two, or one. Advantageously, a weighted average of all four known value lattice point values is used if the given lattice point is enclosed by the tetrahedron but is not touched by a face of the tetrahedron, a weighted average of three of the four known value lattice point values is used if the given lattice point is on a face of the tetrahedron bounded by the three of the four known value lattice points but is not touched by an edge of the tetrahedron, a weighted average of two of the four known value lattice point values is used if the given lattice point is on an edge of the tetrahedron bounded by the two of the four known value lattice points but is not at a vertex of the tetrahedron, and wherein a value of one of the known value lattice points is used if the given lattice point is also the known value lattice point.
In particular embodiments, the average number of table look up operations can be reduced further. For example, where a given lattice point is close to a known value lattice point, the given lattice point may be changed to the known value lattice point hence avoiding need for calculation of any weighted average, thus reducing the number of table look up operations required to one (from, typically, four) for such cases.
Advantageously, the known value lattice points form a sparse lattice with known value lattice points separated from each other by an integer multiple (preferably an integer power of two) of the distance between adjacent lattice points. A particularly preferred value for the integer is 8.
In a preferred approach, the step of establishing a value comprises determining a set of four known value lattice points which form a tetrahedron touching or enclosing the given lattice point, and providing the weighted average from the positions of four known value lattice points, the known values of one or more of the four known value lattice points, and the position of the given lattice point. Advantageously, the step of providing the weighted average comprises using the positions as inputs to a jump table, or similar. (Case statements are used in the specific example described below; use of a computed goto is a further alternative).
The method can be carried out by using a programmed computer, or can be facilitated by providing a programmed memory or storage device that can be accessed by a computer.
The method can advantageously be used for mapping values in a first color space to values in a second color space. However, this is far from the only possible application for this technique. Look up tables are frequently used when the result is known, but cannot be computed from a function (either because the computation is too complex to perform in real time, or because the function itself is unknown). For example, a forward function may exist that, given the result as its parameter, will yield the input value, but the function cannot be used to find the result because the inverse function cannot be found. One solution to the lack of an inverse function is simply to enumerate all the parameters for the forward function and tabulate the results. The table can then be used to perform the inverse function, but if the table is too large to store, it can be stored in a sparse manner and intermediate values calculated by interpolationxe2x80x94this interpolation can be carried out by methods in accordance with the invention.
Use of large look up tables, best stored sparsely, (and hence suitable for application of the invention) may arise in a large number of contexts. In automotive control, engine management systems may well require such look up tables. Medical imaging is a further likely areaxe2x80x94particularly for image reconstruction in tomography (especially soft field electrical tomography). In computer animation, such an approach is particularly appropriate for recovering the parameters that represent the motion of objects in the animation. In image analysis, this approach is particularly suitable to image enhancement and image recognition. The skilled man will appreciate that this general approach may be applied in many other contexts.